package com.klangner.go.app.strategy;

import java.util.Collection;
import java.util.Iterator;

import com.klangner.go.ab.IMoveSelector;
import com.klangner.go.app.rules.BoardModel;
import com.klangner.go.app.rules.GoConstants;
import com.klangner.go.app.rules.IOldMoveSelector;
import com.klangner.go.model.IBoard;
import com.klangner.go.model.Move;



/**
 * This class models the Alpha-Beta Pruning algorithm for game trees: it's
 * an improvement over the classical Min-Max algorithm
 * The idea is to avoid exploration of clearly hopeless branches
 * The result is the same as with Min-Max, but faster (especially
 * when we have a good ordering of the to-be-explored nodes).
 */
public class AlphaBetaPruningGoStrategy implements IGoStrategy {

  //----------------------------------------------------------------------------
  public AlphaBetaPruningGoStrategy( int color,
                                     IGoEstimator estimator,
                                     int maxDepth,
                                     IMoveSelector moveSelector ) {
    this.color = color;
    this.estimator_ = estimator;
    this.moveSelector = moveSelector;
    this.maxDepth = maxDepth;
  }


  //----------------------------------------------------------------------------
  public void setMaxDepth(int newMaxDepth) {
    maxDepth = newMaxDepth;
  }

  //----------------------------------------------------------------------------
  public int getMaxDepth() {
    return maxDepth;
  }

  //----------------------------------------------------------------------------
  private EstimatedMove expandAlphaBeta(BoardModel position, int maxDepth, float alpha, float beta ) {


//        Debug.log("\nStarted expandAlphaBeta; alpha = " + alpha + ", beta = " + beta + " for position = " + position.toString());

        int turn = position.getTurnColor();

        EstimatedMove bestSoFar = new EstimatedMove(new Move(-1, -1, turn),
                                                    Float.NEGATIVE_INFINITY);

        if ( ( maxDepth == 0 ) ||
             ( estimator_.checkPositionState( position ) !=
               GoConstants.InProgress )) {
                // No more branching

            bestSoFar.value_ = estimator_.estimatePosition( position, turn );
            return bestSoFar;
        }


        Collection<Move> candidates = moveSelector.getCandidates(position.getBoard(), turn);

        if ( candidates.size() == 0 ) {

            float estimated = estimator_.estimatePosition( position, turn );
            bestSoFar.value_ = estimated;

        } else {
//            Debug.log("Candidates for next move:");
//            for ( int i = 0; i < candidates.size(); ++i) {
//                Move move = (Move)candidates.elementAt(i);
////                move.color = position.turn();
//
//                BoardModel nextPosition = position.positionAfterMove(
//                    move );
////                Debug.log( nextPosition.toString() );
//            }

        	Iterator<Move> it = candidates.iterator();
            while ( it.hasNext() ) {
                Move currentNextMove = it.next();
  //              currentNextMove.color = position.turn();

                BoardModel nextPosition = position.positionAfterMove(
                    currentNextMove );

                float initialValue = Float.NEGATIVE_INFINITY;

                float value = -(expandAlphaBeta(
                                    nextPosition,
                                    maxDepth - 1,
                                    -beta, -alpha).value_);

                if (bestSoFar.value_ < value)
                {

                    bestSoFar.value_ = value;
                    bestSoFar.move_ = currentNextMove;
                }

                if (alpha < value) {
//                    Debug.log("Alpha is " + alpha + ", smaller than current estimation, " + value + ". Alpha became " + value);
                    alpha = value;
                }

                if ( alpha >= beta )
                {
//                    Debug.log("Alpha is " + alpha + ", >= beta (" + beta + "). Alpha-beta cutoff: estimation returns" + alpha);
                    bestSoFar.value_ = alpha;
                    return bestSoFar;
                }
            }
            bestSoFar.value_ =  alpha;
        }

//        Debug.log( "Alpha-beta returned " + bestSoFar );
        return bestSoFar;
  }


    //----------------------------------------------------------------------------
    // method from GoStrategy interface
    public Move chooseNextMove(BoardModel position) {
        int lastMoveColor = ((position.getTurnColor() == IBoard.BLACK_STONE) ?
                             IBoard.WHITE_STONE : IBoard.BLACK_STONE);

        float initialValue = ((position.getTurnColor() == this.color) ?
                              Float.NEGATIVE_INFINITY :
                              Float.POSITIVE_INFINITY);

        alpha = Float.NEGATIVE_INFINITY;
        beta = Float.POSITIVE_INFINITY;

        EstimatedMove estimatedMove = expandAlphaBeta( position,
                                                       maxDepth,
                                                       alpha, beta );

        return estimatedMove.move_;
    };


  //----------------------------------------------------------------------------
  // Private members
  static class EstimatedMove {
      public EstimatedMove( Move move, float value ){
          move_ = move;
          value_ = value;
      }

      public String toString() {
          return "(" + move_.toString() + " : " + value_ + ")";
      }

      Move move_;
      float value_;
  };

  // The players's color
  // (we need this in order to know when to minimize  and when to
  // maximize positions values)
  // By default, we consider that "color" player tries to maximize, and
  // his oponent to minimize values
  protected int color;

  // a GoEstimatorInterface used to estimate the value of a given position
  protected IGoEstimator estimator_;

  protected float alpha, beta;

  /** Move selector */
  private IMoveSelector moveSelector;
  private int maxDepth = GoConstants.defaultMaxDepth;
}
